package com.bjsxt.datastructure.search;

/**
 * 二分法查找
 * 必须是顺序表（数组），按照某个值的顺序排列
 */
public class TestSearch2 {
    public static void main(String[] args) {

        //给定的数组
        int[] array = {1,2,3,4,5,6,7,8,9,10};
        //查找的值
        int key = 2;
        //二分法查找
        int index = binarySearch(array, key);
        //输出结果
        if (index == -1) {
            System.out.println("没有这个值");
        } else {
            System.out.println(index);
        }
    }

    /**
     * 非递归方法
     * @param array
     * @param key
     * @return
     */
    private static int search(int[] array, int key) {
        int low = 0;
        int height = array.length;
        while (low <= height) {
            int mid = (low + height) / 2;
            if (array[mid] == key) {
                return mid;
            } else if (array[mid] < key) {
                low = mid + 1;
            } else {
                height = mid -1;
            }
        }
        return -1;
    }

    /**
     * 递归方法
     * @param array
     * @param key
     * @return
     */
    private static int binarySearch(int[] array, int key) {
        int low = 0;
        int height = array.length;
        return binarySearch(array, key, low, height);
    }

    private static int binarySearch(int[] array, int key, int low, int height) {
        if (low > height) {
            return -1;
        }
        int mid = (low + height) / 2;
        if (array[mid] == key) {
            return mid;
        } else if (array[mid] > key) {
            return binarySearch(array, key, low, mid - 1);
        } else {
            return binarySearch(array, key, low + 1, height);
        }
    }
}
